package uestc.lj.basicPromotion.dfs;

/**
 * @Author:Crazlee
 * @Date:2021/11/28
 */
public class Code06_CoinsWays {
	public static int coinsWays1(int[] array, int aim) {
		return process(array, 0, aim);
	}

	private static int process(int[] arr, int index, int rest) {
		if (index == arr.length) {
			return rest == 0 ? 1 : 0;
		}
		int ways = 0;
		for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
			ways += process(arr, index + 1, rest - arr[index] * zhang);
		}
		return ways;
	}

	public static int coinsWays2(int[] array, int aim) {
		if (array == null || array.length == 0) {
			return 0;
		}
		int[][] dp = new int[array.length + 1][aim + 1];
		dp[array.length][0] = 1;
		for (int i = 1; i <= aim; i++) {
			dp[array.length][i] = 0;
		}
		for (int index = array.length - 1; index >= 0; index--) {
			for (int rest = 0; rest <= aim; rest++) {
				int ways = 0;
				for (int zhang = 0; array[index] * zhang <= rest; zhang++) {
					ways += dp[index + 1][rest - array[index] * zhang];
				}
				dp[index][rest] = ways;
			}
		}

		return dp[0][aim];
	}


	public static int coinsWays3(int array[], int aim) {
		if (array == null || array.length == 0) {
			return 0;
		}
		int[][] dp = new int[array.length + 1][aim + 1];
		dp[array.length][0] = 1;
		for (int i = 1; i <= aim; i++) {
			dp[array.length][i] = 0;
		}
		for (int index = array.length - 1; index >= 0; index--) {
			for (int rest = 0; rest <= aim; rest++) {
				dp[index][rest] = dp[index + 1][rest];
				if (rest - array[index] >= 0) {
					dp[index][rest] += dp[index][rest - array[index]];
				}
			}
		}
		return dp[0][aim];
	}
}

